package leetcode.LinkedList;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author MaoLin Wang
 * @date 2020/2/1016:42
 */
public class _23MergeKLists {
    public static ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> queue = new LinkedList<ListNode>();
        for (int i = 0; i < lists.length; i += 2) {
            if ((i + 1) == lists.length) {
                queue.offer(lists[i]);
            } else {
                queue.offer(_21MergeTwoLists.mergeTwoLists2(lists[i], lists[i + 1]));

            }
        }
        while (queue.size() > 1) {
            ListNode node = _21MergeTwoLists.mergeTwoLists2(queue.poll(), queue.poll());
            queue.offer(node);
        }
        return queue.poll();
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists==null){
            return null;
        }
        Queue<ListNode> q = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        for (ListNode node : lists) {
            if (node!=null){
                q.offer(node);

            }
        }
        ListNode result=new ListNode(-1);
        ListNode resTemp=result;
        while (!q.isEmpty()){
            ListNode listNode = q.poll();
            resTemp.next=listNode;
            resTemp=resTemp.next;
            if (listNode.next!=null){
                q.offer(listNode.next);
            }
        }
        return result.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(0);
        l1.next = new ListNode(1);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(4);
        l1.next.next.next.next = new ListNode(4);

        ListNode l2 = new ListNode(0);
        l2.next = new ListNode(2);
        l2.next.next = new ListNode(3);
        l2.next.next.next = new ListNode(5);
        l2.next.next.next.next = new ListNode(6);

        ListNode l3 = new ListNode(1);
        l3.next = new ListNode(5);
        l3.next.next = new ListNode(6);
        l3.next.next.next = new ListNode(8);
        l3.next.next.next.next = new ListNode(9);

        ListNode[] listNodes = {l1, l2, l3};
        ListNode node = mergeKLists(listNodes);
        ListNode.printNode(node);


    }

}
